682D - Alyona and Strings - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll m, n, k, f[1005][1005][15][2];
string s, t;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k >> s >> t;
    s = '#'+s;
    t='#'+t;
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            for(int x=0; x<=k; x++){
                for(int y=0; y<=1; y++){
                    f[i][j][x][y] = -1;
                }
            }
        }
    }
    f[0][0][0][0] = 0;
    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            for(int x=0; x<=k; x++){
                for(int y=0; y<=1; y++){
                    if(f[i][j][x][y] == -1) continue;
                    f[i+1][j][x][0] = max(f[i+1][j][x][0], f[i][j][x][y]);
                    f[i][j+1][x][0] = max(f[i][j+1][x][0], f[i][j][x][y]);
                    if(s[i+1]==t[j+1]){
                       f[i+1][j+1][x+1][1] = max(f[i+1][j+1][x+1][1], f[i][j][x][y]+1);
                       if(y==1) f[i+1][j+1][x][1] = max(f[i+1][j+1][x][1], f[i][j][x][y]+1);
                    }
                }
            }
        }
    }
    cout << max(f[n][m][k][0], f[n][m][k][1]);


    return 0;
}